package Hard;

import java.util.HashSet;
import java.util.Set;

// 37.解数独
public class Solution37 {
    public static void main(String[] args) {
        char[][] board = new char[][]{
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'}, {'6', '.', '.', '1', '9', '5', '.', '.', '.'}, {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'}, {'4', '.', '.', '8', '.', '3', '.', '.', '1'}, {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'}, {'.', '.', '.', '4', '1', '9', '.', '.', '5'}, {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};
        solveSudoku(board);
    }

    public static void solveSudoku(char[][] board) {
        /*
            深搜，搞9个行set用于记录每一行出现过的数字
            9个列set用于记录每一列出现过的数字
            9个块set用于记录每一块出现过的数字
            对于board[i,j]，
            遍历0-9，分别填入这个位置，要求这个数没有出现在行set和列set以及块set里
            并把这个数加到行set和列set以及块set里
            如果最后没有填满所有的数字，就往上回溯，尝试回溯地点的下一个数字
        */
        Set<Character>[] rowSet = new Set[9];
        Set<Character>[] colSet = new Set[9];
        Set<Character>[] blockSet = new Set[9];
        for (int i = 0; i < 9; i++) {
            rowSet[i] = new HashSet<Character>();
            colSet[i] = new HashSet<Character>();
            blockSet[i] = new HashSet<Character>();
        }
        // 初始化所有的set
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.')
                    continue;
                // 确认当前是第几块
                int x = i / 3;
                int y = j / 3;
                int curBlock = 3 * x + y;
                // 将数字填入set
                rowSet[i].add(board[i][j]);
                colSet[j].add(board[i][j]);
                blockSet[curBlock].add(board[i][j]);
            }
        }
        char[][] ans = null;
        ans = dfs(board, rowSet, colSet, blockSet, 0, 0, ans);
        board = ans;

        // 打印看结果
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static char[][] dfs(char[][] board, Set[] rowSet, Set[] colSet, Set[] blockSet, int curI, int curJ, char[][] ans) {

        // 如果curI越界了，说明所有的数都填完了,board就是结果
        if (curI == 9) {
            // 将board所有的值赋值给ans
            ans = new char[9][9];
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    ans[i][j] = board[i][j];
                }
            }
            System.out.println("success");
            return ans;
        }
        // 如果curJ越界了，curJ归零，让curI+1
        if (curJ == 9) {
            ans = dfs(board, rowSet, colSet, blockSet, curI + 1, 0, ans);
            return ans;
        }
        // 如果当前数不能填数字，直接跳过
        if (board[curI][curJ] != '.') {
            ans = dfs(board, rowSet, colSet, blockSet, curI, curJ + 1, ans);
            return ans;
        }
        // 确认当前是第几块
        int x = curI / 3;
        int y = curJ / 3;
        int curBlock = 3 * x + y;
        // 递归这个位置所有可以选择的数字
        for (int i = 1; i < 10; i++) {
            if (!rowSet[curI].contains((char) (i + 48)) && !colSet[curJ].contains((char) (i + 48)) && !blockSet[curBlock].contains((char) (i + 48))) {
                // i这个数可以填入这里
                rowSet[curI].add((char) (i + 48));
                colSet[curJ].add((char) (i + 48));
                blockSet[curBlock].add((char) (i + 48));
                board[curI][curJ] = (char) (i + 48);
                ans = dfs(board, rowSet, colSet, blockSet, curI, curJ + 1, ans);
                // 如果ans已经有值了，则不需要找了
                if (ans != null) {
                    return ans;
                }
                // 如果能运行到这里，说明这个位置填这个数是行不通的，所以换下一个数试试吧
                rowSet[curI].remove((char) (i + 48));
                colSet[curJ].remove((char) (i + 48));
                blockSet[curBlock].remove((char) (i + 48));
                board[curI][curJ] = '.';
            }
        }
        // 如果运行到这里，说明没有数字可以选，则本次递归结束，往前回溯
        return ans;
    }
}
